|
In computability theory, a busy beaver is a Turing machine that attains the maximum number of steps performed, or maximum number of nonblank symbols finally on the tape, among all Turing machines in a certain class. The Turing machines in this class must meet certain design specifications and are required to eventually halt after being started with a blank tape. A busy beaver function quantifies these upper limits on a given measure, and is a noncomputable function. In fact, a busy beaver function can be shown to grow faster asymptotically than does any computable function. The concept was first introduced by Tibor Radó as the "busy beaver game" in his 1962 paper, "On Non-Computable Functions". ==The busy beaver game== The ''n''-state busy beaver game (or BB-''n'' game), introduced in Tibor Radó's 1962 paper, involves a class of Turing machines, each member of which is required to meet the following design specifications: *The machine has ''n'' "operational" states plus a Halt state, where ''n'' is a positive integer, and one of the ''n'' states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ..., ''n'', with state 1 as the starting state, or by ''A'', ''B'', ''C'', ..., with state ''A'' as the starting state.) *The machine uses a single two-way infinite (or unbounded) tape. *The tape alphabet is , with 0 serving as the blank symbol. *The machine's ''transition function'' takes two inputs: :#the current non-Halt state, :#the symbol in the current tape cell, :and produces three outputs: :#a symbol to write over the one in the current tape cell (it may be the same symbol as the one overwritten), :#a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and :#a state to transition into (which may be the Halt state). :There are thus ''n''-state Turing machines meeting this definition. :The transition function may be seen as a finite table of 5-tuples, each of the form :(current state, current symbol, symbol to write, direction of shift, next state). "Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the machine eventually halts, then the number of 1s finally remaining on the tape is called the machine's ''score''. The ''n''-state busy beaver (BB-''n'') game is a contest to find such an ''n''-state Turing machine having the largest possible score — the largest number of 1s on its tape after halting. A machine that attains the largest possible score among all ''n''-state Turing machines is called an ''n''-state busy beaver, and a machine whose score is merely the highest so far attained (perhaps not the largest possible) is called a ''champion'' ''n''-state machine. Radó required that each machine entered in the contest be accompanied by a statement of the exact number of steps it takes to reach the Halt state, thus allowing the score of each entry to be verified (in principle) by running the machine for the stated number of steps. (If entries were to consist only of machine descriptions, then the problem of verifying every potential entry is undecidable, because it is equivalent to the well-known halting problem — there would be no effective way to decide whether an arbitrary machine eventually halts.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Busy beaver」の詳細全文を読む スポンサード リンク
|